//143
class Solution {
    public void reorderList(ListNode head) {
        ListNode f = head;
        ListNode s = head;
        while(f != null && f.next != null){
            f = f.next.next;
            s = s.next;
        }
        ListNode prev = null;
        ListNode cur = s;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curN;
        }
        ListNode h2 = prev;
        while(h2 != null && h2.next != null){
            ListNode nxt = head.next;
            ListNode nxt2 = h2.next;
            head.next = h2;
            h2.next = nxt;
            head = nxt;
            h2 = nxt2;
        }
    }
}
//876
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode s = head;
        ListNode f = head;
        while(f != null && f.next != null){
            s = s.next;
            f = f.next.next;
        }
        return s;
    }
}
//25
class Solution {
    public ListNode reverseKGroup(ListNode head, int k){
        //计算链表长度
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }

        //翻转
        ListNode nhead = new ListNode();
        ListNode p0 = nhead;
        p0.next = head;
        cur = p0.next;
        ListNode prev = null;
        for(int i=0; i<count/k; i++){
            for(int j=0; j<k; j++){
                ListNode curNext = cur.next;
                cur.next = prev;
                prev = cur;
                cur = curNext;
            }
            ListNode nxt = p0.next;
            p0.next.next = cur;
            p0.next = prev;
            p0 = nxt;
        }
        return nhead.next;
    }
}
//92
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode nhead = new ListNode();
        ListNode p0 = nhead;
        p0.next = head;
        for(int i = 1; i < left; i++){
            p0 = p0.next;
        }
        ListNode prev = null;
        ListNode cur = p0.next;
        for(int i=1; i<=right-left+1; i++){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        p0.next.next = cur;
        p0.next = prev;
        return nhead.next;
    }
}
public class Test {
}
